// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

// 算法思路总结：
// 1. 回溯算法生成电话号码的字母组合
// 2. 使用哈希表存储数字到字母的映射
// 3. 按数字顺序递归选择每个数字对应的所有字母
// 4. 路径长度等于数字串长度时保存结果
// 5. 时间复杂度：O(4ⁿ)，空间复杂度：O(n)（递归栈深度）

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    string path;
    vector<string> letterCombinations(string digits) 
    {
        if (digits.empty()) return {};
        ret.clear();
        dfs(digits, 0);

        return ret;
    }

    void dfs(string digits, int pos)
    {
        if (path.size() == digits.size())
        {
            ret.push_back(path);
            return ;
        }

        for (int i = 0 ; i < hash[digits[pos] - '0'].size() ; i++)
        {
            path.push_back(hash[digits[pos] - '0'][i]);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

int main()
{
    string digits1 = "23";
    string digits2 = "2";

    Solution sol;
    auto vs1 = sol.letterCombinations(digits1);
    auto vs2 = sol.letterCombinations(digits2);

    for (const string& str : vs1)
        cout << str << " ";
    cout << endl;

    for (const string& str : vs2)
        cout << str << " ";
    cout << endl;

    return 0;
}